Disclaimer: 今年大概撐不到連續 30 天...大概能寫多少就是多少吧 哈哈

1 圖論為什麼重要

1.1 圖論可以幫助你看清問題的本質

圖 (Graph) 是一種抽象的數學模型，它可以用來描述東西與東西之間的關聯。這個『東西』根據想要解決的問題而定，可以有很多意義。而圖論 (Graph Theory) 便是一類將事物簡化成『東西』與『關聯』的模型之後，針對其結構和性質而得出的一套數學理論。

圖一：上面繪製的兩張圖，都是有 6 個點的完全圖，他們雖然看起來不太一樣，但是結構相同：任何兩個點之間都連有一條邊。

1.2 資訊科學裡面哪裡有圖論

簡短的答案：到處都是。比方說最直接的網路模型（設備與設備之間的資料傳輸連結），我們可以利用化簡後的圖論模型找出伺服器流量的瓶頸在哪裡、也可以設計出當某些機器過載的時候資料該如何繞道而行。在非傳統關聯式資料庫 (NoSQL) 中，也有一些專門為稀疏關聯設計出的圖論資料庫模型，比方說 GraphQL 等，在查詢與存儲資料的效能中，比起傳統的關聯式資料庫更能獲得一些優勢。在編譯器的最佳化過程中，也會對如控制流圖和資料流圖等等進行分析，讓該程式編譯後執行效率得以提升。此外，有一些產品天生就與圖論有關，比方說地圖的自動導航功能：該如何引導使用者用最快速度抵達目的地；在倉儲和物流系統中，資源和貨品該如何調度；影像和圖像的匹配與修改，也可以透過圖論模型來設計演算法。

1.x 冷笑話

如果你寫了一份程式碼，放了很久很久，它就會變成一張圖了。為什麼？因為老碼是圖啊...

2 這個系列文打算分享什麼

會用到圖論的常見演算法問題當中的理論和解法。圖論的應用層面有兩種，其中一種應用是把一個題目使用圖論的模型來找出其特性，並且根據這些特性設計出演算法解決該問題。另一種應用則是建立圖論模型後，使用已知的工具（比方說線性規劃、矩陣相乘等等）來解決這些已知的圖論問題。我相信有些朋友會想知道關於 Leetcode 上面的圖論題目要怎麼解，所以如果剛好有涵蓋到相關內容的話，我也會用 Leetcode 的題目作為舉例，這樣大概會有心理上比較踏實的感覺。

如果真的要說實作的技術成分的話，藉由這 30 天，我這次想要學學用 python 的 networkx 這個 package 練習畫圖。